package com.shm.leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

/**
 * @author: shm
 * @dateTime: 2020/11/17 8:47
 * @description: 406. 根据身高重建队列
 * 假设有打乱顺序的一群人站成一个队列。 每个人由一个整数对(h, k)表示，其中h是这个人的身高，k是排在这个人前面且身高大于或等于h的人数。 编写一个算法来重建这个队列。
 *
 * 注意：
 * 总人数少于1100人。
 *
 * 示例
 *
 * 输入:
 * [[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]
 *
 * 输出:
 * [[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]
 */
public class ReconstructQueue {
    /**
     * @author: shm
     * @dateTime: 2020/11/17 10:28
     * @description: 方法一：从低到高考虑
     * 思路与算法
     *
     * 当每个人的身高都不相同时，如果我们将他们按照身高从小到大进行排序，那么就可以很方便地还原出原始的队列了。
     *
     * 为了叙述方便，我们设人数为 nn，在进行排序后，它们的身高依次为 h_0, h_1, \cdots, h_{n-1}h
     * 0
     * ​
     *  ,h
     * 1
     * ​
     *  ,⋯,h
     * n−1
     * ​
     *  ，且排在第 ii 个人前面身高大于 h_ih
     * i
     * ​
     *   的人数为 k_ik
     * i
     * ​
     *  。如果我们按照排完序后的顺序，依次将每个人放入队列中，那么当我们放入第 ii 个人时：
     *
     * 第 0, \cdots, i-10,⋯,i−1 个人已经在队列中被安排了位置，并且他们无论站在哪里，对第 ii 个人都没有任何影响，因为他们都比第 ii 个人矮；
     *
     * 而第 i+1, \cdots, n-1i+1,⋯,n−1 个人还没有被放入队列中，但他们只要站在第 ii 个人的前面，就会对第 ii 个人产生影响，因为他们都比第 ii 个人高。
     *
     * 如果我们在初始时建立一个包含 nn 个位置的空队列，而我们每次将一个人放入队列中时，会将一个「空」位置变成「满」位置，那么当我们放入第 ii 个人时，我们需要给他安排一个「空」位置，并且这个「空」位置前面恰好还有 k_ik
     * i
     * ​
     *   个「空」位置，用来安排给后面身高更高的人。也就是说，第 ii 个人的位置，就是队列中从左往右数第 k_i+1k
     * i
     * ​
     *  +1 个「空」位置。
     *
     * 那么如果有身高相同的人，上述 k_ik
     * i
     * ​
     *   定义中的大于就与题目描述中要求的大于等于不等价了，此时应该怎么修改上面的方法呢？我们可以这样想，如果第 ii 个人和第 jj 个人的身高相同，即 h_i = h_jh
     * i
     * ​
     *  =h
     * j
     * ​
     *  ，那么我们可以把在队列中处于较后位置的那个人的身高减小一点点。换句话说，对于某一个身高值 hh，我们将队列中第一个身高为 hh 的人保持不变，第二个身高为 hh 的人的身高减少 \deltaδ，第三个身高为 hh 的人的身高减少 2\delta2δ，以此类推，其中 \deltaδ 是一个很小的常数，它使得任何身高为 hh 的人不会与其它（身高不为 hh 的）人造成影响。
     *
     * 如何找到第一个、第二个、第三个身高为 hh 的人呢？我们可以借助 kk 值，可以发现：当 h_i=h_jh
     * i
     * ​
     *  =h
     * j
     * ​
     *   时，如果 k_i > k_jk
     * i
     * ​
     *  >k
     * j
     * ​
     *  ，那么说明 ii 一定相对于 jj 在队列中处于较后的位置（因为在第 jj 个人之前比他高的所有人，一定都比第 ii 个人要高），按照修改之后的结果，h_ih
     * i
     * ​
     *   略小于 h_jh
     * j
     * ​
     *  ，第 ii 个人在排序后应该先于第 jj 个人被放入队列。因此，我们不必真的去对身高进行修改，而只需要按照 h_ih
     * i
     * ​
     *   为第一关键字升序，k_ik
     * i
     * ​
     *   为第二关键字降序进行排序即可。此时，具有相同身高的人会按照它们在队列中的位置逆序进行排列，也就间接实现了上面将身高减少 \deltaδ 这一操作的效果。
     *
     * 这样一来，我们只需要使用一开始提到的方法，将第 ii 个人放入队列中的第 k_i+1k
     * i
     * ​
     *  +1 个空位置，即可得到原始的队列。
     *
     * 复杂度分析
     *
     * 时间复杂度：O(n^2)O(n
     * 2
     *  )，其中 nn 是数组 \textit{people}people 的长度。我们需要 O(n \log n)O(nlogn) 的时间进行排序，随后需要 O(n^2)O(n
     * 2
     *  ) 的时间遍历每一个人并将他们放入队列中。由于前者在渐近意义下小于后者，因此总时间复杂度为 O(n^2)O(n
     * 2
     *  )。
     *
     * 空间复杂度：O(\log n)O(logn)，即为排序需要使用的栈空间。
     *
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/queue-reconstruction-by-height/solution/gen-ju-shen-gao-zhong-jian-dui-lie-by-leetcode-sol/
     */
    public int[][] reconstructQueue(int[][] people) {
        Arrays.sort(people, new Comparator<int[]>() {
            @Override
            public int compare(int[] x, int[] y) {
                if (x[0]!=y[0]) {
                    return x[0] - y[0];
                }else{
                    return y[1]-x[1];
                }
            }
        });

        int n = people.length;
        int[][] ans = new int[n][];
        for (int[] person : people) {
            int space = person[1]+1;
            for (int i = 0; i < n; i++) {
                if (ans[i]==null){
                    space--;
                    if (space==0){
                        ans[i]=person;
                        break;
                    }
                }
            }
        }
        return ans;
    }

    /**
     * @author: shm
     * @dateTime: 2020/11/17 10:11
     * @description: 方法二：从高到低考虑
     * 思路与算法
     *
     * 同样地，我们也可以将每个人按照身高从大到小进行排序，处理身高相同的人使用的方法类似，即：按照 h_ih
     * i
     * ​
     *   为第一关键字降序，k_ik
     * i
     * ​
     *   为第二关键字升序进行排序。如果我们按照排完序后的顺序，依次将每个人放入队列中，那么当我们放入第 ii 个人时：
     *
     * 第 0, \cdots, i-10,⋯,i−1 个人已经在队列中被安排了位置，他们只要站在第 ii 个人的前面，就会对第 ii 个人产生影响，因为他们都比第 ii 个人高；
     *
     * 而第 i+1, \cdots, n-1i+1,⋯,n−1 个人还没有被放入队列中，并且他们无论站在哪里，对第 ii 个人都没有任何影响，因为他们都比第 ii 个人矮。
     *
     * 在这种情况下，我们无从得知应该给后面的人安排多少个「空」位置，因此就不能沿用方法一。但我们可以发现，后面的人既然不会对第 ii 个人造成影响，我们可以采用「插空」的方法，依次给每一个人在当前的队列中选择一个插入的位置。也就是说，当我们放入第 ii 个人时，只需要将其插入队列中，使得他的前面恰好有 k_ik
     * i
     * ​
     *   个人即可。
     *   复杂度分析
     *
     * 时间复杂度：O(n^2)O(n
     * 2
     *  )，其中 nn 是数组 \textit{people}people 的长度。我们需要 O(n \log n)O(nlogn) 的时间进行排序，随后需要 O(n^2)O(n
     * 2
     *  ) 的时间遍历每一个人并将他们放入队列中。由于前者在渐近意义下小于后者，因此总时间复杂度为 O(n^2)O(n
     * 2
     *  )。
     *
     * 空间复杂度：O(\log n)O(logn)。
     *
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/queue-reconstruction-by-height/solution/gen-ju-shen-gao-zhong-jian-dui-lie-by-leetcode-sol/
     */
    public int[][] reconstructQueue_2(int[][] people) {
        Arrays.sort(people, new Comparator<int[]>() {
            @Override
            public int compare(int[] x, int[] y) {
                if (x[0]!=y[0]){
                    return y[0]-x[0];
                }else {
                    return x[1]-y[1];
                }
            }
        });
        int n = people.length;
        List<int[]> ans = new ArrayList<>();
        for (int[] person : people) {
            ans.add(person[1],person);
        }
        return ans.toArray(new int[n][]);
    }
}
